package org.basis.algorithm.list.practice;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.SingleNode;

import java.util.Stack;

/**
 * 链表常见问题练习
 *
 * @author Mr_wenpan@163.com 2022/01/05 11:39
 */
public class ListPractice {

    public static void main(String[] args) {
        SingleNode<Integer> head = ListNodeUtil.generateIntegerSingleList(10, 50, true);
        ListNodeUtil.printSingleList(head);
        SingleNode<Integer> newHead1 = reverseByStack(head);
        ListNodeUtil.printSingleList(newHead1);
        SingleNode<Integer> newHead2 = reverseByPoint(newHead1);
        ListNodeUtil.printSingleList(newHead2);

    }

    /**
     * 拼接两个链表
     * 拼接方式：两个链表交错拼接
     */
    public static SingleNode<Integer> combineList(SingleNode<Integer> head1, SingleNode<Integer> head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        SingleNode<Integer> newHead = head1;
        while (head1 != null && head2 != null) {
            SingleNode<Integer> next1 = head1.next;
            SingleNode<Integer> next2 = head2.next;
            head1.next = head2;
            head2.next = next1;
            head1 = next1;
            head2 = next2;
        }
        // 返回拼接后的新头
        return head1;
    }

    /**
     * 通过快慢指针查找链表中点，这里需要注意快慢指针的起始位置，起始位置决定了慢指针最后落在哪个中点
     */
    public static SingleNode<String> findMiddle(SingleNode<String> head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 快慢指针，这里快指针先走出一步，确保fast指针走到头时，slow指针在中点或左中点位置
        // 如果要找中点或右中点的节点，那么快慢指针要同时放置在head处开始走
        SingleNode<String> slow = head;
        SingleNode<String> fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 返回中点
        return slow;
    }

    /**
     * 通过三个指针反转链表
     */
    public static SingleNode<Integer> reverseByPoint(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        SingleNode<Integer> pre = null;
        SingleNode<Integer> cur = head;
        SingleNode<Integer> next;
        while (cur != null) {
            // 暂存next节点
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 返回新的头节点
        return pre;
    }

    /**
     * 通过栈来反转链表
     */
    public static SingleNode<Integer> reverseByStack(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<SingleNode<Integer>> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        // pop一个元素出来作为新的头节点
        SingleNode<Integer> newHead = stack.pop();
        SingleNode<Integer> cur = newHead;
        newHead.next = null;
        while (!stack.isEmpty()) {
            SingleNode<Integer> pop = stack.pop();
            cur.next = pop;
            cur = pop;
            pop.next = null;
        }
        // 返回新的头节点
        return newHead;
    }

    public SingleNode<Integer> reorderList(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 先找到链表的中点(这里快指针起始位置在慢指针前一步，保证循环退出时满指针停在中点或左中点)
        SingleNode<Integer> slow = head;
        SingleNode<Integer> fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 从中点处断开，组成两个链表
        SingleNode<Integer> cur = slow.next;
        SingleNode<Integer> pre = null;
        SingleNode<Integer> next = null;
        slow.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // 合并两个链表
        SingleNode<Integer> newHead = pre;
        SingleNode<Integer> originHead = head;

        while (originHead != null && newHead != null) {
            // 暂存两个链表的下一个节点
            SingleNode<Integer> next1 = originHead.next;
            SingleNode<Integer> next2 = newHead.next;
            originHead.next = newHead;
            newHead.next = next1;
            originHead = next1;
            newHead = next2;
        }
        // 返回合并后链表的头节点
        return head;
    }

    /**
     * 通过栈来实现链表重排
     */
    public SingleNode<Integer> reorderList2(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 找到中点
        SingleNode<Integer> slow = head;
        SingleNode<Integer> fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 从中点后面断开链表，将后半部分添加到栈内
        Stack<SingleNode<Integer>> stack = new Stack<>();
        SingleNode<Integer> temp = slow.next;
        slow.next = null;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        temp = head;
        while (!stack.isEmpty()) {
            SingleNode<Integer> pop = stack.pop();
            SingleNode<Integer> next = temp.next;
            temp.next = pop;
            pop.next = next;
            temp = next;
        }
        return head;
    }

}
